#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_BOARD 3
#define MAX_QUEUE 9
#define MAX_STATES 3*3

typedef struct Node {
    int board[MAX_BOARD][MAX_BOARD];
    int parent[MAX_BOARD][MAX_BOARD];
    int g; // Cost to reach this node
    struct Node* next;
} Node;

Node* queue[MAX_QUEUE];
int front = 0, rear = 0;
int visited[MAX_STATES];
int initial[MAX_BOARD][MAX_BOARD] = { {2, 8, 3}, {1, 6, 4}, {7, 0, 5} };
int goal[MAX_BOARD][MAX_BOARD] = { {1, 2, 3}, {8, 0, 4}, {7, 6, 5} };
int isGoal = 0;

void enqueue(Node* node) {
    queue[rear++] = node;
}

Node* dequeue() {
    return queue[front++];
}

int isEmpty() {
    return front == rear;
}

int hashValue(int board[MAX_BOARD][MAX_BOARD]) {
    int hash = 0;
    for (int i = 0; i < MAX_BOARD; i++)
        for (int j = 0; j < MAX_BOARD; j++)
            hash += board[i][j] * pow(10, (3 * i + j));
    return hash;
}

void initializeVisited() {
    memset(visited, 0, sizeof(visited));
    visited[hashValue(initial)] = 1;
}

Node* createNode(int board[MAX_BOARD][MAX_BOARD], int parent[MAX_BOARD][MAX_BOARD]) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    for (int i = 0; i < MAX_BOARD; i++)
        for (int j = 0; j < MAX_BOARD; j++) {
            newNode->board[i][j] = board[i][j];
            newNode->parent[i][j] = parent[i][j];
        }
    newNode->g = 0; // Initialize cost
    newNode->next = NULL;
    return newNode;
}

int findBlank(int board[MAX_BOARD][MAX_BOARD]) {
    for (int i = 0; i < MAX_BOARD; i++)
        for (int j = 0; j < MAX_BOARD; j++)
            if (board[i][j] == 0)
                return i * MAX_BOARD + j;
    return -1;
}

void move(int board[MAX_BOARD][MAX_BOARD], int direction, int blankX, int blankY, int newBoard[MAX_BOARD][MAX_BOARD]) {
    switch (direction) {
    case 0: // Up
        newBoard[blankX - 1][blankY] = board[blankX][blankY];
        newBoard[blankX][blankY] = 0;
        break;
    case 1: // Down
        newBoard[blankX + 1][blankY] = board[blankX][blankY];
        newBoard[blankX][blankY] = 0;
        break;
    case 2: // Left
        newBoard[blankX][blankY - 1] = board[blankX][blankY];
        newBoard[blankX][blankY] = 0;
        break;
    case 3: // Right
        newBoard[blankX][blankY + 1] = board[blankX][blankY];
        newBoard[blankX][blankY] = 0;
        break;
    }
}

void generateSuccessors(Node* node) {
    int blankX, blankY, newBoard[MAX_BOARD][MAX_BOARD];
    blankX = findBlank(node->board) / MAX_BOARD;
    blankY = findBlank(node->board) % MAX_BOARD;

    int directions[4] = { 0, 1, 2, 3 }; // Up, Down, Left, Right
    for (int i = 0; i < 4; i++) {
        int newX = blankX + (blankX > 0 ? -1 : 1) * (directions[i] == 0);
        newX += (blankX < 2 ? 1 : -1) * (directions[i] == 1);
        int newY = blankY + (blankY > 0 ? -1 : 1) * (directions[i] == 2);
        newY += (blankY < 2 ? 1 : -1) * (directions[i] == 3);

        if (newX >= 0 && newX < MAX_BOARD && newY >= 0 && newY < MAX_BOARD) {
            memcpy(newBoard, node->board, sizeof(newBoard));
            move(node->board, directions[i], blankX, blankY, newBoard);
            int newHash = hashValue(newBoard);
            if (!visited[newHash]) {
                visited[newHash] = 1;
                int parent[MAX_BOARD][MAX_BOARD];
                memcpy(parent, node->parent, sizeof(parent));
                parent[blankX][blankY] = node->board[blankX][blankY];
                Node* newNode = createNode(newBoard, parent);
                enqueue(newNode);
            }
        }
    }
}

void printPath(Node* node) {
    if (node->parent[0][0] != -1) {
        printPath(node->parent);
    }
    for (int i = 0; i < MAX_BOARD; i++) {
        for (int j = 0; j < MAX_BOARD; j++) {
            printf("%d ", node->board[i][j]);
        }
        printf("\n");
    }
    printf("\n");
}

void bfs() {
    Node* root = createNode(initial, goal);
    enqueue(root);
    while (!isEmpty()) {
        Node* current = dequeue();
        if (memcmp(current->board, goal, sizeof(goal)) == 0) {
            isGoal = 1;
            printPath(current);
            return;
        }
        generateSuccessors(current);
    }
    if (!isGoal) {
        printf("No solution found.\n");
    }
}

int main() {
    initializeVisited();
    bfs();
    return 0;
}